package dataStructure.Recursion;

/**
 * @author lhn
 * @date 2024-08-28 16:22
 */

public class EightQueens {

    //定义一个max 变量，表示共有多少个皇后
    int max = 8;
    //定义数组array，保存皇后放置位置的结果
    int array[] = new int[max]; //一维数组，下标表示第几列（行），值表示第几行（列）
    static int count = 0;  //记录摆放方法的个数
    public static void main(String[] args) {
        new EightQueens().check(0);
        System.out.println("总共有" + count + "种摆放方法");
    }

    //放置第n个皇后
    public void check(int n) {
        if (n == max) {
            print();
            count ++;
            return;
        }

        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前这个皇后摆放到第i行的第一列位置
            array[n] = i;
            //判断第n个皇后是否和前面皇后冲突
            if (judge(n)) {
                check(n+1);
            }
            //如果冲突，就回到上一个皇后继续摆放
        }
    }


    /**
    * 检查摆放的第n个皇后与之前的皇后是否冲突
    * @author lihaonan
    * @date 2024/8/28 17:00
     * @param n
     * @return boolean
     * true ：不冲突
     * false：冲突
    */
    public boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            //判断条件一：是否在同一行
            //判断条件二：是否在同一斜线，斜率是否为1（x轴上的距离和y轴上的距离是否相等，相等斜率的绝对值为1）
            if (array[i] == array[n]
                    || Math.abs(n-i) == Math.abs(array[i]-array[n])) {
                return false;
            }
        }
        return true;
    }
    //打印皇后摆放的位置
    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}
